#include <bits/stdc++.h>
using namespace std;

/*
1611. 使整数变为 0 的最少操作次数
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

翻转 n 的二进制表示中最右侧位（第 0 位）。
如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。
返回将 n 转换为 0 的最小操作次数。

 

示例 1：

输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。
示例 2：

输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。
 

提示：

0 <= n <= 109
*/

// 法一
class Solution {
public:
    int minimumOneBitOperations(int n) {
        // 必须推导 直接去模拟深度太高 
        if (n == 0) return 0;
        int k = 31 - __builtin_clz(n);
        int pow2k = 1 << k;
        // Func : (2^(k+1)-1) - f(n-2^k)
        return (pow2k << 1) - 1 - minimumOneBitOperations(n - pow2k);
    }
};

// 法二
class Solution {
public:
    using ll = long long;
    int minimumOneBitOperations(int n) {
        // 必须推导 直接去模拟深度太高 
        if (n == 0) return 0;
        // 找最高位
        int k = 0;
        ll pow2k = 1;
        while (pow2k * 2 <= n) {
            pow2k <<= 1;
            k++;
        }
        // Func : (2^(k+1)-1) - f(n-2^k)
        return (pow2k << 1) - 1 - minimumOneBitOperations(n - pow2k);
    }
};

// 法三
// 无 迭代会超时